package personal.leil.learning.exercises;

import personal.leil.learning.SNode;
import personal.leil.learning.utils.LinkedListUtils;

/**
 * 打印两个有序链表的公共部分
 * <p>
 *     给定两个有序链表的头指针head1和head2，打印两个链表的公共部分。
 *     如果两个链表的长度之和为N，时间复杂度要求为O(N)，额外空间复杂度要求为O(1)
 * </p>
 */
public class Question1 {


    public static void process(SNode head1, SNode head2) {
        SNode current1 = head1;
        SNode current2 = head2;
        while (current1 != null && current2 != null) {
            if ((int)current1.getData() > (int)current2.getData()) {
                current2 = current2.getNext();
            } else if ((int)current1.getData() < (int)current2.getData()) {
                current1 = current1.getNext();
            } else {
                System.out.println(current1.getData());
                current1 = current1.getNext();
                current2 = current2.getNext();
            }
        }
    }

    /********************* For Test *************************/

    public static void main(String[] args) {
        SNode head1 = LinkedListUtils.buildSingleLinkedList(new int[]{2, 3, 4, 6, 8, 9, 11});
        SNode head2 = LinkedListUtils.buildSingleLinkedList(new int[]{1, 3, 4, 5, 7, 9});
        process(head1, head2);
    }


}
